package 数据结构OJ;

import java.util.*;

/**
 * @author shy_black
 * @date 2019/7/28 17:54
 * @Description:
 *
 * 利用LinkedList底层是双向链表的结构，在每层插入一个null,遇到null以后，以flag决定正向或反向遍历节点，
 * 向ArrayList中添加这一层元素，改变flag，即可完成之字形打印二叉树
 */
public class 按之字形顺序打印二叉树 {

    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        ArrayList<Integer> out = new ArrayList<>();
        LinkedList<TreeNode> tree = new LinkedList<>();

        if (pRoot == null) {
            return queue;
        }
        tree.addLast(null);
        tree.addLast(pRoot);
        boolean leftToRight = true;

        while (tree.size() != 1) {
            TreeNode node = tree.removeFirst();
            if (node == null) {
                Iterator<TreeNode> it = null;
                if (leftToRight) {
                    it = tree.iterator();//从前往后遍历
                } else {
                    it = tree.descendingIterator();//从后往前遍历
                }
                leftToRight = !leftToRight;
                while (it.hasNext()) {
                    TreeNode tmp = it.next();
                    out.add(tmp.val);
                }
                queue.add(new ArrayList<Integer>(out));
                out.clear();
                tree.addLast(null);
                continue;
            }
            if (node.left != null) {
                tree.addLast(node.left);
            }
            if (node.right != null) {
                tree.addLast(node.right);
            }
        }
        return queue;
    }
}